package com.mapull.simple;

import java.util.Arrays;

/**
 * 插入排序
 * @author mapull
 * @date 2022-06-05
 */
public class Insertion {

    public static void main(String[] args) {
        int[] nums = {5,9,7,4,6,1,3,2,8};
        System.out.println("排序前 " + Arrays.toString(nums));
        insertionSort(nums);
        System.out.println("排序后 " + Arrays.toString(nums));
    }

    private static void insertionSort(int[] nums) {
        // i 代表待插入元素的位置，假设第一个元素已经排序完成，索引从 1 开始
        for (int i = 1; i < nums.length; i++) {
            // 待插入的元素值
            int tmp = nums[i];
            // 已排序区域的最后一个元素位置
            int j = i - 1;
            // 把 tmp 元素放到已排序区域的合适位置
            while (j >= 0){
//                System.out.print("比较 " + tmp + " 与 " + nums[j] + "; ");
                if(tmp < nums[j]){
                    nums[j + 1] = nums[j];
                }else {
                    break;
                }
                j--;
            }
//            System.out.println();
            nums[j+1] = tmp;
            System.out.println(Arrays.toString(nums));
        }
    }
}
